
#include "fft.h"
// FFT su dung giai thuat butter fly demension 2....
// Noted: Demension 2 chua toi uu  can su dung 


void fft(float *real, float *img, long n, float *tmpReal, float *tmpImg)
{
  if(n>1) {			/* n <2 thi thoat ko de quy nua */
	  long k, m;    float zReal, zImg, wReal,wImg, *voReal, *veReal, *voImg, *veImg;
	  voReal = tmpReal; veReal = tmpReal + n / 2;
	  voImg = tmpImg; veImg = tmpImg + n / 2;
	// Don dong lai chan le .
	for(k=0; k<n/2; k++) {
		veImg[k] = img[2 * k];
		veReal[k] = real[2 * k];

		voReal[k] = real[2 * k + 1];
		voImg[k] = img[2 * k + 1];
	}

	fft(veReal, veImg, n / 2, real, img);		
	fft(voReal, voImg, n / 2, real, img);		
	for(m=0; m<n/2; m++) {
	// Noted: chua toi uu cho can fix ma tran w ... FFT se duoc goi nhieu lan viec tinh toan se lau .
	  	wReal = cos(2 * PI*m / (double)n);
		wImg = -sin(2 * PI*m / (double)n);
		zReal = wReal*voReal[m] - wImg*voImg[m];	
		zImg = wReal*voImg[m] + wImg*voReal[m];	

		real[m] = veReal[m]+zReal; // Canh tren
		img[m] = veImg[m] + zImg; // Canh tren
	  
		real[m + n/2] = veReal[m] - zReal; // Canh tren
		img[m + n/2] = veImg[m] - zImg; // Canh tren

	}
  }

  return;
}
 


void ifft(float *real, float *img, long n, float *tmpReal, float *tmpImg)
{
  if(n>1) {			/* otherwise, do nothing and return */
	  long k, m;    float zReal, zImg, wReal, wImg, *voReal, *veReal, *voImg, *veImg;
	  voReal = tmpReal; veReal = tmpReal + n / 2;
	  voImg = tmpImg; veImg = tmpImg + n / 2;
	for (k = 0; k<n / 2; k++) {
		veImg[k] = img[2 * k];
		veReal[k] = real[2 * k];

		voReal[k] = real[2 * k + 1];
		voImg[k] = img[2 * k + 1];
	}
	ifft(veReal, veImg, n / 2, real, img);		
	ifft(voReal, voImg, n / 2, real, img);		
	for(m=0; m<n/2; m++) {
		//Noted: Can tang performance -> fix thanh ma tran
		wReal = cos(2 * PI*m / (double)n);
		wImg =  sin(2 * PI*m / (double)n);
		zReal = wReal*voReal[m] - wImg*voImg[m];	
		zImg = wReal*voImg[m] + wImg*voReal[m];	

		real[m] = veReal[m] + zReal; // Canh tren
		img[m] = veImg[m] + zImg; // Canh tren

		real[m + n / 2] = veReal[m] - zReal; // Canh tren
		img[m + n / 2] = veImg[m] - zImg; // Canh tren
	}
  }
  return;
}

